#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>
#include <linux/limits.h>
#include <error.h>
#include <errno.h>

// 存储文件详细信息的结构体
typedef struct FileInfo {
    char *path;               // 文件完整路径
    off_t size;               // 文件大小
    time_t mtime;             // 最后修改时间
    struct FileInfo *next;    // 用于链接同名文件
} FileInfo;

// 二叉树节点结构体
typedef struct TreeNode {
    char *filename;           // 文件名（用于排序）
    FileInfo *files;          // 同名文件的链表
    struct TreeNode *left;    // 左子树
    struct TreeNode *right;   // 右子树
} TreeNode;

// 创建新的文件信息节点
FileInfo* createFileInfo(const char *path, off_t size, time_t mtime) {
    FileInfo *file = (FileInfo*)malloc(sizeof(FileInfo));
    if (!file) {
        perror("malloc failed");
        return NULL;
    }
    
    // 分配路径内存并复制
    file->path = strdup(path);
    if (!file->path) {
        perror("strdup failed");
        free(file);
        return NULL;
    }
    
    file->size = size;
    file->mtime = mtime;
    file->next = NULL;
    
    return file;
}

// 创建新的二叉树节点
TreeNode* createTreeNode(const char *filename, FileInfo *file) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (!node) {
        perror("malloc failed");
        return NULL;
    }
    
    // 分配文件名内存并复制
    // strdup 计算输入字符串的长度(包括'\0') 使用malloc分配足够的内存空间 
    //        将字符串的内容复制到新内存 返回指向新字符串的指针
    node->filename = strdup(filename);
    if (!node->filename) {
        perror("strdup failed");
        free(node);
        return NULL;
    }
    
    node->files = file;
    node->left = NULL;
    node->right = NULL;
    
    return node;
}

// 向二叉树中插入文件信息
TreeNode* insertFile(TreeNode *root, const char *filename, FileInfo *file) {
    if (root == NULL) {
        // 创建新节点
        return createTreeNode(filename, file);
    }
    
    int cmp = strcmp(filename, root->filename);
    
    if (cmp < 0) {
        // 文件名小于当前节点，插入左子树
        root->left = insertFile(root->left, filename, file);
    } else if (cmp > 0) {
        // 文件名大于当前节点，插入右子树
        root->right = insertFile(root->right, filename, file);
    } else {
        // 文件名相同，将当前节点创建为链表头节点
        // 找到链表末尾，插入新的文件信息
        FileInfo *current = root->files;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = file;
    }
    
    return root;
}

// 递归扫描目录并索引文件
void indexDirectory(TreeNode **root, const char *dirPath) {
    // 新增目录是否可以访问(检查权限)
    if(access(dirPath, R_OK) == -1){
        // 只提示权限错误，不终止程序
        if(errno == EACCES){
            fprintf(stderr, "警告：没有权限访问目录 %s (跳过)\n", dirPath);
        }else {
            fprintf(stderr, "警告：无法访问目录 %s: %s (跳过)\n", dirPath, strerror(errno));
        }
        return;
    }
    
    DIR *dir = opendir(dirPath);
    if (!dir) {
        //perror("无法打开目录");
        fprintf(stderr, "警告: 无法打开目录 %s: %s (跳过)\n", dirPath, strerror(errno));
        return;
    }
    
    struct dirent *entry;
    // readdir 从目标流读取下一个目录项
    while ((entry = readdir(dir)) != NULL) {
        // 跳过当前目录(.)和父目录(..)
        if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0) {
            continue;
        }
        
        // 构建完整路径
        char fullPath[PATH_MAX];
        // 把目录和当前文件名拼接到完整路径
        snprintf(fullPath, sizeof(fullPath), "%s/%s", dirPath, entry->d_name); 
        fullPath[PATH_MAX - 1] = '\0';  // 确保路径终止符

        // 获取文件信息
        struct stat fileStat; // 存储获取到的文件信息
        if (lstat(fullPath, &fileStat) == -1) { // 改用 lstat 避免跟随符号链接
            fprintf(stderr, "警告: 无法获取文件信息 %s: %s (跳过)\n", fullPath, strerror(errno));
            continue;
        }
        
        // 如果是目录，则递归处理，st_mode文件类型和权限
        if (S_ISDIR(fileStat.st_mode)) {
            indexDirectory(root, fullPath);
        } 
        // 如果是普通文件，则添加到索引
        else if (S_ISREG(fileStat.st_mode)) {
            // 创建文件信息节点
            FileInfo *file = createFileInfo(fullPath, fileStat.st_size, fileStat.st_mtime);
            if (file) {
                // 插入到二叉树
                *root = insertFile(*root, entry->d_name, file);
            }
        }
    }
    
    closedir(dir);
}

// 在二叉树中查找文件
TreeNode* findFile(TreeNode *root, const char *filename) {
    if (root == NULL) {
        return NULL;
    }
    
    int cmp = strcmp(filename, root->filename);
    
    if (cmp < 0) {
        return findFile(root->left, filename);
    } else if (cmp > 0) {
        return findFile(root->right, filename);
    } else {
        // 找到匹配的文件名
        return root;
    }
}

// 显示文件信息
void displayFileInfo(FileInfo *file) {
    if (file == NULL) 
    {
        printf("文件不存在\n");
        return;
    }
    // 转换时间格式，localtime 将 time_t 类型的时间戳转换为本地类型的 tm 结构体
    // tm 结构体包含年、月、日、时、分、秒
    struct tm *timeinfo = localtime(&file->mtime);
    char timeStr[20];
    // strftime 将 tm 结构体转换为自定义字符串
    strftime(timeStr, sizeof(timeStr), "%Y-%m-%d %H:%M:%S", timeinfo);
    
    printf("  路径: %s\n", file->path);
    printf("  大小: %ld 字节\n", (long)file->size);
    printf("  修改时间: %s\n", timeStr);
    printf("  ------------------------------\n");
}

// 显示查找结果
void displaySearchResult(TreeNode *node) {
    if (!node) {
        printf("未找到该文件\n");
        return;
    }
    
    // 统计同名文件数量
    int count = 0;
    FileInfo *current = node->files;
    while (current) {
        count++;
        current = current->next;
    }
    
    printf("找到 %d 个名为 '%s' 的文件:\n", count, node->filename);
    printf("--------------------------------------\n");
    
    // 显示所有同名文件信息
    current = node->files;
    while (current) {
        displayFileInfo(current);
        current = current->next;
    }
}

// 中序遍历二叉树，按文件名排序显示
void inOrderTraversal(TreeNode *root) {
    if (root == NULL) return;
    
    inOrderTraversal(root->left);
    
    printf("文件名: %s\n", root->filename);
    FileInfo *current = root->files;
    while (current) {
        printf("  %s\n", current->path);
        current = current->next;
    }
    printf("\n");
    
    inOrderTraversal(root->right);
}

// 释放文件信息链表
void freeFileInfo(FileInfo *file) {
    while (file) {
        FileInfo *temp = file;
        file = file->next;
        free(temp->path);
        free(temp);
    }
}

// 释放二叉树
void freeTree(TreeNode *root) {
    if (root == NULL) return;
    
    freeTree(root->left);
    freeTree(root->right);
    
    freeFileInfo(root->files);
    free(root->filename);
    free(root);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "请正确使用,用法: %s + 目录路径\n", argv[0]);
        return 1;
    }
    
    // 检查目录是否存在
    struct stat dirStat;
    if (stat(argv[1], &dirStat) == -1) {
        fprintf(stderr, "错误: 目录 '%s' 不存在或无法访问: %s\n", argv[1], strerror(errno));
        return 1;
    }
    if (!S_ISDIR(dirStat.st_mode)) {
        fprintf(stderr, "错误: '%s' 不是目录\n", argv[1]);
        return 1;
    }
    
    TreeNode *root = NULL;
    
    printf("正在扫描目录: %s\n", argv[1]);
    printf("正在建立文件索引，请稍候...\n");
    printf("（注意：扫描系统目录如/usr可能会因权限问题跳过部分子目录）\n");
    
    // 索引目录中的所有文件
    indexDirectory(&root, argv[1]);
    
    printf("索引建立完成！\n");
    printf("请输入要查询的文件名（输入 'q' 退出，输入 'l' 列出所有文件）: ");
    
    char filename[256];
    while (1) {
        if (fgets(filename, sizeof(filename), stdin) == NULL) {
            break;
        }
        
        // 去除换行符
        //filename[strcspn(filename, '\n')] = '\0';
        size_t len = strlen(filename);
        if (len > 0 && filename[len - 1] == '\n') {
            filename[len - 1] = '\0';
        }

        // 退出条件
        if (strcmp(filename, "q") == 0) {
            break;
        }
        // 列出所有文件
        else if (strcmp(filename, "l") == 0) {
            printf("\n所有索引文件(按文件名排序):\n");
            printf("===============================\n");
            inOrderTraversal(root);
            printf("===============================\n");
        }
        // 查找文件
        else if (len > 0) {
            TreeNode *result = findFile(root, filename);
            displaySearchResult(result);
        }
        
        printf("\n请输入要查询的文件名(输入 'q' 退出，输入 'l' 列出所有文件): ");
    }
    
    // 释放内存
    freeTree(root);
    printf("\n程序已退出\n");
    
    return 0;
}
